Image registration is the process of determining a relationship between pixel elements in a pair of images that have common subject matter. Image registration is an important method in fields such as image matching, satellite imagery and medical imagery. In image matching, two images are compared for common subject matter based on an assumption that some geometrical transformation relates substantial portions of the two images. Determining some parameterised form of the relating transformation is the image registration process.
Image registration may be applied in a number of contexts. For example, image registration is applied in camera calibration, where an image of a known object is captured and the location of that known object within the image is calculated to determine some unknown parameters of the imaging device. Image registration may also be applied in video sequence registration, where the image registration may form part of a system for determining the relative video camera orientation and position between video frames. Image registration may also be applied in document authentication, where the visual characteristics of a document are matched against digital signatures in a database to verify the authenticity of the document.
A simple form of image registration may be used when the two images are related through translation only. In such a case, an error minimization method may be used to determine the translation relating the two images. For example, two images, f1(x, y), and f2(x, y) may be functions of pixel coordinates x and y. The unknown shift between the images may be determined by searching for a global minimum of an error function according to Equation (1) below:
                              E          ⁡                      (                                          x                0                            ,                              y                0                                      )                          =                              ∑                          x              ,              y                                ⁢                                    (                                                                    f                    1                                    ⁡                                      (                                          x                      ,                      y                                        )                                                  -                                                      f                    2                                    ⁡                                      (                                                                  x                        +                                                  x                          0                                                                    ,                                              y                        +                                                  y                          0                                                                                      )                                                              )                        2                                              (        1        )            where
      ∑          x      ,      y        ⁢      (    )  denotes a summation over the pixel coordinates of the whole image. Expanding the square of Equation (1) leads to Equation (2) below:
                              E          ⁡                      (                                          x                0                            ,                              y                0                                      )                          =                                            ∑                              x                ,                y                                      ⁢                                                            f                  1                                ⁡                                  (                                      x                    ,                    y                                    )                                            2                                +                                    ∑                              x                ,                y                                      ⁢                                                            f                  2                                ⁡                                  (                                                            x                      +                                              x                        0                                                              ,                                          y                      +                                              y                        0                                                                              )                                            2                                -                      2            ⁢                                          ∑                                  x                  ,                  y                                            ⁢                                                                    f                    1                                    ⁡                                      (                                          x                      ,                      y                                        )                                                  ⁢                                                      f                    2                                    ⁡                                      (                                                                  x                        +                                                  x                          0                                                                    ,                                              y                        +                                                  y                          0                                                                                      )                                                                                                          (        2        )            where the first term of Equation (2) is constant. The second term of Equation (2) is also constant under the assumption of periodic boundary conditions which will apply when the Fast Fourier Transform (FFT) is used to do the matching. The third term constitutes a cross-correlation C(x0, y0) according to Equation (3) below:
                              C          ⁡                      (                                          x                0                            ,                              y                0                                      )                          =                              ∑                          x              ,              y                                ⁢                                                    f                1                            ⁡                              (                                  x                  ,                  y                                )                                      ⁢                                          f                2                            ⁡                              (                                                      x                    +                                          x                      0                                                        ,                                      y                    +                                          y                      0                                                                      )                                                                        (        3        )            
When the cross correlation C(x0, y0) is a maximum, then the error between the two images, f1(x, y) and f2(x, y), will be a minimum. Hence, finding a peak in the correlation between two images is the same as minimising the error function between the two images.
Cross-correlation is generally performed using the FFT. For an image f(x, y), the discrete Fourier transform ℑ(f) is defined according to Equation (4) below:
                              F          ⁡                      (                          u              ,              v                        )                          =                              ∑                          x              =              0                                      N              x                                ⁢                                          ⁢                                    ∑                              y                =                0                                            N                y                                      ⁢                                                  ⁢                                          f                ⁡                                  (                                      x                    ,                    y                                    )                                            ⁢                              ⅇ                                                      -                    2                                    ⁢                                                                          ⁢                  π                  ⁢                                                                          ⁢                  ⅈ                  ⁢                                                                          ⁢                                      xu                    /                                          N                      x                                                                                  ⁢                              ⅇ                                                      -                    2                                    ⁢                                                                          ⁢                  π                  ⁢                                                                          ⁢                  ⅈ                  ⁢                                                                          ⁢                                      yv                    /                                          N                      y                                                                                                                              (        4        )            where Nx and Ny are the image dimensions in the x and y dimensions respectively. The inverse discrete Fourier transform ℑ−1(F) is defined according to Equation (5) below:
                                              ⁢                                          ⁢                          (              F              )                                =                                    1                                                N                  x                                ⁢                                  N                  y                                                      ⁢                                          ∑                                  u                  =                  0                                                  N                  x                                            ⁢                                                          ⁢                                                ∑                                      v                    =                    0                                                        N                    y                                                  ⁢                                                                  ⁢                                                      F                    ⁡                                          (                                              u                        ,                        v                                            )                                                        ⁢                                      ⅇ                                          2                      ⁢                                                                                          ⁢                      π                      ⁢                                                                                          ⁢                      ⅈ                      ⁢                                                                                          ⁢                                              xu                        /                                                  N                          x                                                                                                      ⁢                                      ⅇ                                          2                      ⁢                                                                                          ⁢                      π                      ⁢                                                                                          ⁢                      ⅈ                      ⁢                                                                                          ⁢                                              yv                        /                                                  N                          y                                                                                                                                                                            (        5        )            
The FFT is a computationally efficient method of calculating the Discrete Fourier Transform ℑ(f) and the inverse Discrete Fourier Transform ℑ−1(F).
A cross-correlation C may be determined according to Equation (6) below:C=ℑ−1(ℑ(f1)ℑ(f2)*)  (6)where ℑ(f2)* denotes the complex conjugation of the Discrete Fourier Transform ℑ(f2).
Thus, taking the inverse FFT ℑ−1( ) of the product of the FFT of one image ℑ(f1) and the complex conjugate of the FFT of the other image ℑ(f2)* leads to a further image which contains the values of the cross-correlation C which is equivalent to that defined in Equation (3).
While cross-correlation is an effective method of detecting the translation between two images, cross-correlation cannot handle a large area of modifications from one image to another. In the case of two images of a scene with multiple moving objects, for example, cross-correlation may fail to give a correct translation of stationary parts of the scene if the moving objects cover a significant percentage of the total image area. In another example, within the field of document authentication, an image of a physical medium may undergo substantial modifications, such as printing, after an initial digital signature was captured. In this instance, the modified area is likely to have a strong influence on the matching of the digital signatures and naturally, the larger the modified area, the stronger the influence of the modified area.
To deal with modified pixels when correlating two images, a non-negative-valued weight 0≦αi(x, y)≦1 is associated with each pixel fi(x, y) in both images (i=1, 2). This weight represents a degree of influence of each pixel to the alpha-weighted error function defined according to Equation (7) below:
                              e          ⁡                      (                                          x                0                            ,                              y                0                                      )                          =                              ∑                          x              ,              y                                ⁢                                          ⁢                                                    (                                                                            f                      1                                        ⁡                                          (                                              x                        ,                        y                                            )                                                        -                                                            f                      2                                        ⁡                                          (                                                                        x                          +                                                      x                            0                                                                          ,                                                  y                          +                                                      y                            0                                                                                              )                                                                      )                            2                        ⁢                                          α                1                            ⁡                              (                                  x                  ,                  y                                )                                      ⁢                                          α                2                            ⁡                              (                                                      x                    +                                          x                      0                                                        ,                                      y                    +                                          y                      0                                                                      )                                                                        (        7        )            
Similar to the cross-correlation case, the alpha-masked correlation value e(x0, y0) may be expressed as a sum of three correlations by expanding the square term in Equation (7) and distributing the square term according to Equation (8) below:
                              e          ⁡                      (                                          x                0                            ,                              y                0                                      )                          =                                            ∑                              x                ,                y                                      ⁢                                                            α                  1                                ⁡                                  (                                      x                    ,                    y                                    )                                            ⁢                                                f                  1                  2                                ⁡                                  (                                      x                    ,                    y                                    )                                            ⁢                                                α                  2                                ⁡                                  (                                                            x                      +                                              x                        0                                                              ,                                          y                      +                                              y                        0                                                                              )                                                              -                      2            ⁢                                          ∑                                  x                  ,                  y                                            ⁢                                                          ⁢                                                                    f                    1                                    ⁡                                      (                                          x                      ,                      y                                        )                                                  ⁢                                                      f                    2                                    ⁡                                      (                                                                  x                        +                                                  x                          0                                                                    ,                                              y                        +                                                  y                          0                                                                                      )                                                  ⁢                                                      α                    1                                    ⁡                                      (                                          x                      ,                      y                                        )                                                  ⁢                                                      α                    2                                    ⁡                                      (                                                                  x                        +                                                  x                          0                                                                    ,                                              y                        +                                                  y                          0                                                                                      )                                                                                +                                    ∑                              x                ,                y                                      ⁢                                                  ⁢                                                            α                  1                                ⁡                                  (                                      x                    ,                    y                                    )                                            ⁢                                                f                  2                  2                                ⁡                                  (                                                            x                      +                                              x                        0                                                              ,                                          y                      +                                              y                        0                                                                              )                                            ⁢                                                α                  2                                ⁡                                  (                                                            x                      +                                              x                        0                                                              ,                                          y                      +                                              y                        0                                                                              )                                                                                        (        8        )            
Let the symbol  denote the correlation of two functions g and h according to Equation (9) below:
                                          (                          g              ⊗              h                        )                    ⁢                      (            m            )                          =                              ∑            x                    ⁢                                          ⁢                                    g              ⁡                              (                x                )                                      ⁢                                          h                *                            ⁡                              (                                  x                  +                  m                                )                                                                        (        9        )            where * is the complex conjugate. Equation (8) may be re-written as a sum of three correlations according to Equation (10) below:e(x0,y0)=(α1f12α2−2α1f1α2f2+α1f22α2)(x0,y0)  (10)
The alpha-masked correlation value e(x0, y0) is often normalized by the number of terms used in the calculation of the error function at each translation (x0, y0) according to Equation (11) as follows:
                              ɛ          ⁡                      (                                          x                0                            ,                              y                0                                      )                          =                              (                                                                                α                    1                                    ⁢                                                            f                      1                      2                                        ⊗                                          α                      2                                                                      -                                  2                  ⁢                                                                          ⁢                                      α                    1                                    ⁢                                                            f                      1                                        ⊗                                          α                      2                                                        ⁢                                      f                    2                                                  +                                                                            α                      1                                        ⊗                                          f                      2                      2                                                        ⁢                                      α                    2                                                                                                α                  1                                ⊗                                  α                  2                                                      )                    ⁢                      (                                          x                0                            ,                              y                0                                      )                                              (        11        )            
If both images have zero local mean, the first and third terms in Equation (11) approach the variances of the images, which are constant. The second term in Equation (11) constitutes a normalized correlation value according to Equation (12) below:
                              c          ⁡                      (                                          x                0                            ,                              y                0                                      )                          =                                                            α                1                            ⁢                                                f                  1                                ⊗                                  α                  2                                            ⁢                              f                2                                                                    α                1                            ⊗                              α                2                                              ⁢                      (                                          x                0                            ,                              y                0                                      )                                              (        12        )            
Similar to the case of cross-correlation, the normalized correlation value c(x0, y0) is a maximum when the alpha-weighted error function between the two images reaches a minimum. Hence, determining a peak in the normalized correlation between two alpha-masked images is the same as minimising the alpha-weighted error function between the two alpha-masked images.
While the translation between two images can be detected using correlation methods, two images f1(x, y) and f2(x, y) may be related by a rotation and a scale transformation, such that image f2(x, y) is a rotated and scaled version of the image f1(x, y) according to Equation (13) below:f2(x,y)=f1(s(x cos θ+y sin θ),s(−x sin θ+y cos θ))  (13)where s is a scale factor and θ is a rotation angle, the unknown rotation θ and scale s parameters may be determined by transforming the images f1(x, y) and f2(x, y) into a log-polar coordinate space according to Equations (14) below:
                              ρ          =                                    1              2                        ⁢                          log              ⁡                              (                                                      x                    2                                    +                                      y                    2                                                  )                                                    ⁢                                  ⁢                  ϕ          =                                    tan                              -                1                                      ⁢                          y              x                                                          (        14        )            
The transformation above leads to a relationship between the images f1(x, y) and f2(x, y) in the log-polar space according to Equation (15) below:f2(ρ,φ)=f1(ρ+log s,φ∂),  (15)
The correlation methods described above may then be used to determine the scale and rotation parameters s and θ from the peak in the correlation C at coordinate (log s, θ).
The two images f1(x, y) and f2(x, y) can also be related by a combination of Rotation, Scaling, and Translation (RST) transformation according to Equation (16) below:f2(x,y)=f1(s(x cos θ+y sin θ)+Δx,s(−x sin θ+y cos θ)+Δy)  (16)where s is a scale factor, θ is a rotation angle, and (Δx, Δy) are translation in x and y directions. The unknown rotation θ and scale s parameters may be determined from translation invariant representations Tf 1 and Tf2 of the images f1(x, y) and f2(x, y), correspondingly. For example, a recombination of the Fourier magnitude |F| and the Laplacian of the Fourier phase ∇2φ is invariant to any translation applied to the constituting image f according to Equation (17) below:Tf=|F|+iA∇2φ  (17)where A is a scaling constant set according to Equation (18) below:A=max(|F|)/π  (18)to ensure that the recombined Fourier magnitude and phase information are roughly of equal magnitude.
After the rotation θ and scale s parameters are determined, the image f2(x, y) can be transformed to correct for the rotation and scaling. The translation parameters (Δx, Δy) can then be estimated from the image f1(x, y) and the transformed image f2(x, y) using the previously described correlation methods.
However, the conventional methods of registering images related by translation, rotation and scale, as described above, do not handle modifications across images very well, especially when the modified areas are significant.